/**
 * 双向链表
 *   -- 可以从头遍历到尾，又可以从尾遍历到头
 *   -- 一个节点既有向前连接的引用，也有一个向后连接的引用
 *
 *   -- 可以使用一个head和一个tail分别指向头部和尾部的节点
 *   -- 每个节点由三部分组成，前一个结点的指针（prev）/保存的元素（item）/后一个节点的指针（next）
 *   -- 双向链表的第一个节点的prev是null
 *   -- 双向链表的最后一个节点的next是null
 *
 *   缺点：
 *     - 每次在插入或者删除某个节点时，需要处理四个引用，而不是两个，实现起来比较困难
 *     - 相对于单向链表，占用内存空间更大一些
 */

/**
 * 双向链表常见操作：
 *   - append(element):向列表尾部添加一个新的项
 *   - insert(position,element): 向列表特定位置添加一个新的项
 *   - get(position):获取对应位置的元素
 *   - indexOf(element):返回元素在列表的索引，如果不存在就返回-1
 *   - update(position,element):修改某个位置的元素
 *   - removeAt(position):从列表特定位置移除一项
 *   - remove(element):从列表中移除一项
 *   - isEmpty():如果链表中不包含任何元素就返回true，否则返回false
 *   - size():返回链表中包含的元素个数，与数组length属性相似
 *   - toString():由于列表使用了Node类，就需要重写继承自js对象默认的toString方法，让其只输出元素的值。
 *   - forwardString():返回正向遍历的节点字符串形式
 *   - backwordString():返回反向遍历的节点字符串形式
 */

//封装双向链表

function DoublyLinkedList() {
    //  内部类：节点类
    function Node(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }

    //属性
    this.head = null;
    this.tail = null;
    this.length = 0;

    //1.append方法
    DoublyLinkedList.prototype.append = function (data) {
        //1.根据data创建节点
        var newNode = new Node(data);
        //2.判断添加的是否是第一个节点
        if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }
        //3.length + 1
        this.length++;
    }
    //2.将链表转为字符串形式
    DoublyLinkedList.prototype.toString = function () {
        return this.backwardString();
    }
    DoublyLinkedList.prototype.forwardString = function () {
        var current = this.tail;
        var resultString = '';
        //依次向前遍历，获取每一个节点
        while (current) {
            resultString += current.data;
            current = current.prev;
        }
        return resultString.toString();
    }
    DoublyLinkedList.prototype.backwardString = function () {
        //定义变量
        var current = this.head;
        var resultString = '';
        //依次向后遍历，获取每一个节点
        while (current) {
            resultString += current.data;
            current = current.next;
        }
        return resultString.toString();
    }
    //insert方法
    DoublyLinkedList.prototype.insert = function (position, data) {
        //1。越界判断
        if (position < 0 || position > this.length) return false;
        //2.根据data创建新的节点
        var newNode = new Node(data);
        //3.判断原来的列表是否为空
        if (this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            //3.1判断position是否为0
            if (position === 0) {
                this.head.prev = newNode; //原来第一个节点的prev = newNode
                newNode.next = this.head; //newNode的next = 原来的第一个节点
                this.head = newNode; //最后把head指向新插入的节点
            } else if (position === this.length) { //3.2插入到最后一个节点
                newNode.prev = this.tail;
                this.tail.next = newNode;
                this.tail = newNode;
            } else { //插入到链表中任意位置（除首尾外）
                var current = this.head;
                var index = 0;
                while (index++ < position) {
                    current = current.next;
                }
                //修改指针
                newNode.next = current;
                newNode.prev = current.prev;
                current.prev.next = newNode;
                current.prev = newNode;
            }
        }
        //插入成功，
        this.length++;
        return true;
    }
    //4.get方法,获取对应位置的元素
    DoublyLinkedList.prototype.get = function (position) {
        //1.越界判断
        if (position < 0 || position >= this.length) return null;
        //2.获取元素
        var left = this.length / 2 - 1;
        if (left >= position) {
            //前往后遍历
            var current = this.head;
            var index = 0;
            while (index++ < position) {
                current = current.next;
            }
            return current.data;
        } else {
            //后往前遍历
            var tailCurrent = this.tail;
            var tailIndex = this.length - 1;
            while (tailIndex-- <= position && tailIndex >= left) {
                console.log(tailCurrent, 999);
                tailCurrent = tailCurrent.prev;
            }
            return tailCurrent.data;
        }
    }


}


var doubleList = new DoublyLinkedList();
doubleList.append(0);
doubleList.append(1);
doubleList.append(2);
doubleList.append(3);
doubleList.append(4);
doubleList.append(5);
doubleList.append(6);
doubleList.append(7);
console.log(doubleList.toString());
console.log(doubleList.get(6));